﻿using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_124 : BaseProblem
    {
        public override object GetResult()
        {
            const int max = 100000;
            const int index = 10000;

            var dct = new Dictionary<long, List<long>>();

            long mx = 0;

            for (var n = 1; n <= max; n++)
            {
                var tmp = MathLogic.GetPrimeFactors(n);
                long rs = 1;
                foreach (var pair in tmp)
                {
                    rs *= pair.Key;
                }
                if (dct.ContainsKey(rs))
                {
                    dct[rs].Add(n);
                }
                else
                {
                    dct.Add(rs, new List<long>(){n});
                }
                if (rs > mx)
                    mx = rs;
            }
            var res = new List<long>();

            for (var n = 1; n <= max; n++)
            {
                if(!dct.ContainsKey(n)) continue;
                foreach (var l in dct[n])
                {
                    res.Add(l);
                }
            }

            return res[index-1];
        }

        public override string Problem
        {
            get
            {
                return @"The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23  32  7, so rad(504) = 2  3  7 = 42.

If we calculate rad(n) for 1  n  10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:

Unsorted
 	
Sorted

n

rad(n)


n

rad(n)

k
1
1
 	
1
1
1
2
2
 	
2
2
2
3
3
 	
4
2
3
4
2
 	
8
2
4
5
5
 	
3
3
5
6
6
 	
9
3
6
7
7
 	
5
5
7
8
2
 	
6
6
8
9
3
 	
7
7
9
10
10
 	
10
10
10
Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.

If rad(n) is sorted for 1  n  100000, find E(10000).";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 21417;
            }
        }

    }
}
